package base;

/**
 * @author mazouri
 * @create 2021-12-27 13:19
 */
public class _5_minDistance {
    public int f(char[] w1, int i, char[] w2, int j) {
        if (i == -1 || j == -1) return Math.max(i, j) + 1;
        if (w1[i] == w2[j]) return f(w1, i - 1, w2, j - 1);
        else return Math.min(Math.min(
                f(w1, i - 1, w2, j - 1),    //替换
                f(w1, i - 1, w2, j)),   //删除
                f(w1, i, w2, j - 1)) + 1;   //插入
    }
    public int minDistance(String word1, String word2) {
        char[] w1 = word1.toCharArray(), w2 = word2.toCharArray();
        return f(w1, word1.length() - 1, w2, word2.length() - 1);
    }

    public static void main(String[] args) {
       String word1 = "intention";
       String word2 = "execution";
        _5_minDistance o = new _5_minDistance();
        System.out.println(o.minDistance(word1, word2));
    }
}
